package homework002;

import java.util.Arrays;

/**
 * 需求二
 * 创建一个数组，数组中有 10, 21, 23, 34, 55, 36, 7, 18, 9 ,101, 88
 * 使用冒泡算法或快排算法进行排序
 * 使用二分查找算法找到 34 和 55 在数组中所处的位置
 *
 * @author itheima
 */
public class Main {
    public static void main(String[] args) {
        int[] arr = {10, 21, 23, 34, 55, 36, 7, 18, 9, 101, 88};

        //System.out.println("冒泡排序结果");
        //System.out.println(Arrays.toString(bubbleSort(arr)));

        System.out.println("快速排序结果");
        System.out.println(Arrays.toString(quiteSort(arr, 0, arr.length - 1)));

        int position1 = search(arr, 34);
        int position2 = search(arr, 55);

        System.out.println("34所在位置:" + position1 + ", 55所在位置:" + position2);
    }

    /**
     * 冒泡排序算法
     *
     * @param arr 数组
     * @return 排序后的数组
     */
    private static int[] bubbleSort(int[] arr) {
        //数组长度为5时，需要进行4轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.println("===开始第" + i + "轮比较===");
            //内层循环就是实际循环比较的
            //-1 是为了让数组不要越界
            //-i 每一轮结束之后,我们就会少比一个数字.

            //每一进行完一轮比较，需要比较的次数减一次
            // 第1轮比较4次
            // 第2轮比较3次
            // ...
            for (int j = 0; j < arr.length - 1 - i; j++) {
                System.out.println("进行第" + i + "轮的第" + j + "次比较。");

                //如果当前位置数字 > 下一位数字，则双方调换顺序
                //如果需求是结果从大到小，则这里符号改变一下就行
                if (arr[j] > arr[j + 1]) {
                    //temp作为临时变量，用作交换用
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }

                // 如果当前位置数字 < 下一位数字，则双方位置不变
            }

            System.out.println("===结束第" + i + "轮比较===");
            System.out.println(" ");
        }

        return arr;
    }

    /**
     * 快速排序算法
     *
     * @param arr   数组
     * @param left  左指针位置
     * @param right 右指针位置
     * @return 排序后的数组
     */
    private static int[] quiteSort(int[] arr, int left, int right) {
        // left: 左边箭头指向位置
        // right: 右边箭头指向位置

        // 递归结束的条件
        if (right < left) {
            return arr;
        }

        int left0 = left;
        int right0 = right;

        // 计算出基准数
        int baseNumber = arr[left0];

        // 轮数
        int round = 1;

        // 结束条件是 左边箭头指向 = 右边箭头指向
        while (left != right) {
            //1. 从右开始找比基准数小的（确定右侧箭头停留的位置）
            //判断： 如果右边箭头指的数值 > 基准数 并且 右边箭头在左边箭头之后 -> 继续执行
            // 第一次：arr[9] = 8，是否大于基准数？是；并且 right > left -> 继续执行
            // 第二次：arr[8] = 10，是否大于基准数？是；并且 right > left -> 继续执行
            // 第三次：arr[7] = 5，是否大于基准数？否；-> right 停留在 7 的位置
            while (arr[right] >= baseNumber && right > left) {
                right--;
            }

            //2. 从左开始找比基准数大的（确定左边箭头停留的位置）
            //判断：如果左边箭头指的数值 < 基准数 并且 右边箭头在左边箭头之后 -> 继续执行
            // 第一次：arr[0] = 6，是否<=基准数？是； --> 继续执行
            // 第二次：arr[1] = 1，是否<=基准数？是； --> 继续执行
            // 第三次：arr[2] = 2，是否<=基准数？是； --> 继续执行
            // 第四次：arr[3] = 7，是否<=基准数？否； --> 左侧箭头停留在 3 的位置
            while (arr[left] <= baseNumber && right > left) {
                left++;
            }

            //3. 交换两个值的位置
            // 第一次交换：left: arr[3] = 7, right: arr[7] = 5
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            System.out.println("第" + (round++) + "轮执行结果");
            System.out.println("当前指针位置: left:" + left + ", right:" + right);
        }

        //基准数归位
        int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;

        System.out.println("=====基准数归位=====");
        System.out.println("");

        // 递归调用自己,将左半部分排好序
        quiteSort(arr, left0, left - 1);

        // 递归调用自己,将右半部分排好序
        quiteSort(arr, left + 1, right0);

        return arr;
    }

    /**
     * 二分查找算法
     *
     * @param arr    数组
     * @param number 被查找的数值
     * @return 数值所在的位置
     */
    private static int search(int[] arr, int number) {
        //1,定义查找的范围
        int min = 1;
        int max = arr.length - 1;

        //2.循环查找 min <= max
        while (min <= max) {
            //3.计算出中间位置 mid
            int mid = (max + min) / 2;

            System.out.println("start: 中位数:" + mid + ", 数值为:" + arr[mid] + ", 起始为:" + min + ", 截至为:" + max);

            //mid指向的元素 > number
            if (arr[mid] > number) {
                //表示要查找的元素在左边.
                max = mid - 1;
            } else if (arr[mid] < number) {
                //mid指向的元素 < number
                //表示要查找的元素在右边.
                min = mid + 1;
            } else {
                //mid指向的元素 == number
                return mid;
            }

            System.out.println("end: 中位数:" + mid + ", 数值为:" + arr[mid] + ", 起始为:" + min + ", 截至为:" + max);
        }

        //如果min大于了max就表示元素不存在,返回-1.
        return -1;
    }
}